/**
  \file dawggenerator.cpp
  \author Francis Girard
  \date 6 march 2012
  
  Dawg generator implementation
*/


/*
 *  Copyright (C) 2012, Francis Girard
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 *  Copyright (C) 2011, Jerzy Chalupski
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <string>
#include <iostream>
#include <fstream>
#include <stdexcept>
//#include <array>

#include "polarssl/sha1.h"
#include "dawgbits.h"

//typedef std::array<unsigned char, E_DAWG_HASH_SIZE> Hash;
//typedef unsigned char[E_DAWG_HASH_SIZE] Hash;
typedef unsigned char* Hash;

class GraphNode;
typedef std::set<GraphNode*, bool(*)(const GraphNode*, const GraphNode*)>
        UniqueNodeSet;

// Forward decl.
bool CompareByHashThenDirect(const GraphNode* one,
                             const GraphNode* other);



/**
  Read the word list from the specified file.
  
  The format is one word per line.
  
  A word may be expression containing white characters...
  @param pkcWordListFileName The file name form which to read the word list.
  @param output All the read words as output in the same order as they have been
                read.
*/
std::vector<std::string> ReadWordList
(
  const char* pkcWordListFileName,
  std::vector<std::string>& output
)
{
  std::string word;
  std::ifstream input(pkcWordListFileName);
  if (!input.is_open())
  {
    throw std::ios_base::failure("Cannot open word list");
  }
  while (input.good())
  {
    //input >> word;
    getline(input, word);
    
    if (input.good())
    {
      // Strip left and right just in case
      word.erase(word.begin() + (word.find_last_not_of(" \n\r\t")+1),
                 word.end());
      word.erase(word.begin(),
                 word.begin() + word.find_first_not_of(" \n\r\t"));
      
      output.push_back(word);
    }
  }
  input.close();
  return output;
}


/**
  Sort less-than predicate.
  
  Comparison is first made according to the length of the strings and then
  alphabetically in case of lenght equality.
  
  \param one First word to compare.
  \param other Second word to compare.
  \return True iff one is "less than" second.
*/
bool SortByLengthThenAlphabetically(const std::string &one,
                                    const std::string &other)
{
  if (one.length() == other.length())
  {
    return one.compare(other) < 0;
  }
  else
  {
    return one.length() < other.length();
  }
}


/**
  Computes a checksum for the specified 
  
*/
template <class Iter>
void CalculateWordListChecksum(Iter first, Iter last, Hash result)
{
  if (last - first == 1)
  {
    std::string word = *first;
    //sha1((unsigned char*)word.c_str(), word.length(), result.data());
    sha1((unsigned char*)word.c_str(), word.length(), result);
  }
  else
  {
    //std::array<unsigned char, E_DAWG_HASH_SIZE * 2> mergedHashes;
    unsigned char mergedHashes[E_DAWG_HASH_SIZE * 2];

    Iter middle = first + (last - first) / 2;

    unsigned char leftHash[E_DAWG_HASH_SIZE];
    unsigned char rightHash[E_DAWG_HASH_SIZE];
    CalculateWordListChecksum(first, middle, leftHash);
    CalculateWordListChecksum(middle, last, rightHash);
    
    //merge(leftHash.cbegin(), leftHash.cend(), rightHash.cbegin(),
    //      rightHash.cend(), mergedHashes.begin());
    std::merge(leftHash, leftHash + E_DAWG_HASH_SIZE,
               rightHash, rightHash + E_DAWG_HASH_SIZE,
               mergedHashes);

    sha1(mergedHashes, E_DAWG_HASH_SIZE * 2, result);
  }
}




void encodeGraph
(
  const std::vector<GraphNode*>& rvpIndexedNodes,
  const char* pkcEncodedFileName
)
{
  unsigned int nNb1BytesNodes = 0;
  unsigned int nNb2BytesNodes = 0;
  unsigned int nNb3BytesNodes = 0;
  unsigned int nNb4BytesNodes = 0;
  
  std::ofstream output(pkcEncodedFileName, std::ofstream::out |
                                           std::ofstream::binary);
  
  if (!output.is_open())
  {
    throw std::ios_base::failure("Cannot open binary file");
  }
  
  int numberOfNodes = rvpIndexedNodes.size() + 1;
  output.write(reinterpret_cast<char*>(&numberOfNodes), sizeof(int));
  
  int emptyZeroNode = 0;
  output.write(reinterpret_cast<char*>(&emptyZeroNode), sizeof(int));
  
  std::vector<GraphNode*>::const_iterator itCur = rvpIndexedNodes.begin();
  for ( ; itCur != rvpIndexedNodes.end(); ++itCur )
  {
    //
    // FIXME: It may be worthwhile to implement this to reduce size a bit ...
    //
    if ((*itCur)->hasChild())
    {
      int nDiff = (*itCur)->getDiffIndexWithFstChild();
      int encoded = (*itCur)->encoded();
      if (-127 <= nDiff && nDiff <= 128)
      {
        output.write(reinterpret_cast<char*>(&encoded), 2);
        nNb2BytesNodes++;
      }
      else if (-32767 <= nDiff && nDiff <= 32768)
      {
        output.write(reinterpret_cast<char*>(&encoded), 3);
        nNb3BytesNodes++;
      }
      else
      {
        output.write(reinterpret_cast<char*>(&encoded), sizeof(int));
        nNb4BytesNodes++;
      }
    }
    else
    {
      unsigned char cVal = (*itCur)->getValue();
      output.write((char*) (&cVal), sizeof(char));
      nNb1BytesNodes++;
    }
  }
  
  
  std::cout << "nNb1BytesNodes=" << nNb1BytesNodes << std::endl;
  std::cout << "nNb2BytesNodes" << nNb2BytesNodes << std::endl;
  std::cout << "nNb3BytesNodes" << nNb3BytesNodes << std::endl;
  std::cout << "nNb4BytesNodes" << nNb4BytesNodes << std::endl;
  
  output.close();
}


void findWordsInBinaryNodes
(
  int *nodes,
  int position,
  std::string prefix,
  std::vector<std::string>& output
) 
{
  int node = nodes[position];
  
  char letter = node & E_DAWG_LETTER_MASK;
  int childIndex = (node & E_DAWG_CHILD_INDEX_MASK) >> E_DAWG_CHILD_BIT_SHIFT;
  bool endOfList = (node & E_DAWG_END_OF_LIST_FLAG) != 0;
  bool endOfWord = (node & E_DAWG_END_OF_WORD_FLAG) != 0;
  
  if (endOfWord)
  {
    output.push_back(std::string(prefix + letter));
  }
  
  if (!endOfList)
  {
    findWordsInBinaryNodes(nodes, position + 1, prefix, output);
  }
  
  if (childIndex != 0)
  {
    findWordsInBinaryNodes(nodes, childIndex, prefix + letter, output);
  }
}


/**
  Test that encoded dawg has the expected specified checksum.
  \param expectedChecksum The expected checksum.
  \param pkcEncodedFileName The of the file containing the encoded dawg.
  \return true iff test is successful.
*/
bool testEncodedGraph
(
  const Hash& expectedChecksum,
  const char* pkcEncodedFileName
)
{
  std::ifstream input(pkcEncodedFileName, std::ifstream::in | std::ifstream::binary);
  if (!input.is_open())
  {
    throw std::ios_base::failure("Cannot open binary file");
  }
  
  int nodeCount;
  input.read(reinterpret_cast<char*>(&nodeCount), sizeof(int));
  int *nodes = new int[nodeCount];
  for (int i(0); i != nodeCount; ++i)
  {
    input.read(reinterpret_cast<char*>(nodes + i), sizeof(int));
  }
  input.close();
  
  std::vector<std::string> wordList;
  findWordsInBinaryNodes(nodes, 1, "", wordList);
  
  sort(wordList.begin(), wordList.end(), SortByLengthThenAlphabetically);
  unsigned char binaryOutput[E_DAWG_HASH_SIZE];
  CalculateWordListChecksum(wordList.begin(), wordList.end(), binaryOutput);
  bool bTestOk = std::equal(binaryOutput, binaryOutput + E_DAWG_HASH_SIZE,
                            expectedChecksum);
  
  delete [] nodes;
  return bTestOk;
}


/**
  Generate a binary dawg file from a list of words read from file.
  \param pkcWordListFileName The name of the file containing the list of words
                             to encode into a dawg
  \param pkcEncodedFileName The name of the output file to create.
  \return 0 iff successful.
*/
extern "C" int generate_dawg
(
  const char* pkcWordListFileName,
  const char* pkcEncodedFileName,
  const unsigned char bPrintTrie
)
{
  try
  {
    /*                        */
    /* Read the list of words */
    /*                        */
    printf("Reading word list\n");
    std::vector<std::string> allWords;
    ReadWordList(pkcWordListFileName, allWords);
    
    /*                                                  */
    /* Sort the words by length and then alphabetically */
    /* We need them arranged that way to apply coherent */
    /* node reduction afterward.                        */
    /*                                                  */
    sort(allWords.begin(), allWords.end(), SortByLengthThenAlphabetically);
    int maxWordLength = allWords.back().length();
    
    /*                                                                       */
    /* Calculate the input checksum so that we may check that the list of    */
    /* words reconstructed from the dawg has the same checksum (for testing) */
    /*                                                                       */
    printf("Calculate input checksum\n");
    unsigned char inputChecksum[E_DAWG_HASH_SIZE];
    CalculateWordListChecksum(allWords.begin(), allWords.end(), inputChecksum);
    
    /*                                          */
    /* Create a basic trie from input word list */
    /*                                          */
    printf("Creating a trie\n");
    GraphNode rootNode;
    rootNode.buildTrie(allWords);
    
    if (bPrintTrie)
    {
      std::cout << rootNode;
    }
    
    rootNode.markFirstAndLastChild();
    
    printf("Calculating hash for all nodes\n");
    rootNode.calculateHash();
    
    printf("Removing redundant nodes\n");
    rootNode.reduceGraph(maxWordLength - 1);
    
    printf("Preparing final node list\n");
    std::vector<GraphNode*> indexedNodes;
    rootNode.indexNodes(indexedNodes);
    assert(indexedNodes.size() < (E_DAWG_CHILD_INDEX_MASK >> DAWG_CHILD_BIT_SHIFT));
    printf("Will save %d nodes\n", indexedNodes.size());
    
    /*                                                    */
    /* Encode the acyclic graph into a binary format file */
    /*                                                    */
    printf("Encoding graph\n");
    encodeGraph(indexedNodes, pkcEncodedFileName);
    
    /*                                                            */
    /* Verify that the checksum from dawg math the one from input */
    /*                                                            */
    printf("Testing procedure - recreate from binary file\n");
    bool bTestOk = testEncodedGraph(inputChecksum, pkcEncodedFileName);
    
    /*                         */
    /* If checksum test failed */
    /*                         */
    if (!bTestOk)
    {
      printf("Checksum for list of words fetched from dwag doesn't match "
             "the input one.\n");
      return -1;
    }
  }
  catch (std::exception& e)
  {
    printf("%s\n", e.what());
    return -1;
  }
  
  return 0;
}


